package com.itheima.exerciseTest.test10_19;

import java.util.Arrays;
import java.util.Random;

public class Test16 {
    public static void main(String[] args) {
//        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9,};
//        System.out.println(getIndex(arr, 0));


        for (int i = 0; i < 20; i++) {
            int[] arr = setArray(20, 0, 20);
            System.out.println(Arrays.toString(arr));
            sortArray(arr, 0, arr.length - 1);
            System.out.println(Arrays.toString(arr) + "\n");
        }

    }

    // 创建int数组
    public static int[] setArray(int length, int start, int end) {
        Random r = new Random();
        if (start > end) {
            start = start + end;
            end = start - end;
            start = start - end;
        }
        end += 1;
        int[] arr = new int[length];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = r.nextInt(end - start) + start;
        }
        return arr;

    }

    // 查找给定元素索引
    public static int getIndex(int[] arr, int num) {
        int min = 0;
        int max = arr.length - 1;
        int dim;
        while (min <= max) {
            dim = (min + max) / 2;
            if (arr[dim] > num) {
                max = dim - 1;
            } else if (arr[dim] < num) {
                min = dim + 1;
            } else {
                return dim;
            }
        }
        return -1;
    }

    // 打印数组
    public static void printArray(int[] arr) {
        String s = Arrays.toString(arr);
        System.out.println(s);
    }

    // 递归快排
    public static void sortArray(int[] arr, int left, int right) {
        // 递归出口
        if (left > right) {
            return;
        }
        int left0 = left;
        int right0 = right;

        int baseNumber = arr[left];
        while (left != right) {
            // 比较左边
            while (baseNumber <= arr[right] && right > left) {
                right--;
            }
            // 比较右边
            while (baseNumber >= arr[left] && left < right) {
                left++;
            }
            // 交换赋值
            int tamp = arr[left];
            arr[left] = arr[right];
            arr[right] = tamp;
        }
        int tamp = arr[left];
        arr[left] = arr[left0];
        arr[left0] = tamp;

        sortArray(arr, left0, left - 1);
        sortArray(arr, left + 1, right0);

    }
}
